Теорема о СКНФ. Следствие о КНФ

Любая булева функция, не равная константе $1$, задается некоторой СКНФ.

Пусть $f(x_1, \dots, x_k)$ отлична от константы $1$. Построим СКНФ $F$ по следующему правилу: для каждого битового вектора $\vec{b} = (b_1, \dots, b_k)$ такого, что $f(b_1, \dots, b_k) = 0$, поместим в $F$ элементарную дизъюнкцию $D_{\vec{b}} = x_1^{\bar{b}_1} \lor \dots \lor x_k^{\bar{b}_k}$. Построенная формула — СКНФ по определению. Докажем, что $F$ задает $f$. Функция, заданная КНФ, равна $0 \iff$ одна из элементарных дизъюнкций равна $0$. Тогда выполняется: $$f(b_1, \dots, b_k) = 0 \iff D_{\vec{b}}(b_1, \dots, b_k) = 0$$ $\square$

Любая булева функция задается некоторой КНФ.

Для функций, отличных от $1$, это следует из теоремы выше. Для константы $1$: $x \lor \bar{x}$ — КНФ, задающая $1$.